package org.sample.algorithm.heap;

import java.util.concurrent.ThreadLocalRandom;

/**
 * Created by alan on 2017/7/13.
 * 1.若i为奇数且i>1，那么tree的左兄弟为tree[i-1]
 * 2.若i为偶数且i<n，那么tree的右兄弟为tree[i+1]
 * 3.若i>1，tree的父亲节点为tree[i div 2]
 * 4.若2*i<=n，那么tree的左孩子为tree[2*i]；若2*i+1<=n，那么tree的右孩子为tree[2*i+1]
 * 5.若i>n div 2,那么tree[i]为叶子结点
 * 6.若i<(n-1) div 2.那么tree[i]必有两个孩子
 * 7.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
 */
public class Heap {

    public static void main(String[] args) {
//        Heap<Integer> heap = new Heap<>(1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12, 17, 34, 11);
        Heap heap = new Heap(20);
        for (Integer i = 0; i < 20; i++) {
            heap.push(ThreadLocalRandom.current().nextInt(0, 99));
        }

        Integer size = heap.size();
        for (Integer i = 0; i < size; i++) {
            System.out.print(heap.pop() + ", ");
        }
    }

    private Integer size = 0;

    private Integer[] array;

    public Heap(Integer capacity) {
        this.size = 0;
        this.array = new Integer[capacity];
    }

    public Heap(Integer... array) {
        this.size = array.length;
        this.array = array.clone();
        init();
    }

    private void init() {
        Integer lastParent = (size - 1) >> 1;
        for (Integer i = lastParent; i >= 0; i--) {
            shiftDown(i);
        }
    }

    public Integer push(Integer num) {
        array[size] = num;
        shiftUp(size++);
        return num;
    }

    public Integer pop() {
        Integer result = array[0];
        array[0] = array[--size];
        array[size] = null;
        shiftDown(0);
        return result;
    }

    public Integer peek() {
        return array[0];
    }

    public Integer size() {
        return size;
    }

    /**
     * 将当前节点的值与两个子节点比较
     * 若大于两个子节点其中较小的一个，则与其交换位置
     */
    private void shiftDown(Integer root) {
        Integer left, right;
        while ((left = (root << 1) + 1) < size) {
            right = left + 1;
            if (right < size && array[right].compareTo(array[left]) < 0)
                left = right;
            if (array[root].compareTo(array[left]) > 0) {
                swap(root, left);
                root = left;
            } else {
                break;
            }
        }
    }

    /**
     * 将当前节点的值和父节点比较
     * 若小于父节点则交换位置
     */
    private void shiftUp(Integer current) {
        Integer parent;
        while ((parent = (current - 1) >> 1) >= 0) {
            if (array[current].compareTo(array[parent]) < 0) {
                swap(current, parent);
                current = parent;
            } else {
                break;
            }
        }
    }

    /**
     * 交换两个元素的位置
     */
    private void swap(Integer a, Integer b) {
        Integer t = array[a];
        array[a] = array[b];
        array[b] = t;
    }

}